# 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
#
#  示例 :
# 给定二叉树
#
#           1
#          / \
#         2   3
#        / \
#       4   5
#  返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
from com.example.tree.tree_node import TreeNode


class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        """
        直径可能不穿过根节点
        如下面的直径为[8, 7, 4, 2, 5, 9, 6]长度为 6 就不经过根节点
                1
               / \
              2   3
             / \
            4   5
           /     \
          7       9
         /         \
        8           6
        :param root:
        :return:
        """
        self.res = 1
        def getMaxDepth(root: TreeNode) -> int:
            """
            后序遍历获取当前树的最大深度，并在每次到左右子树的深度之和再加一之后，就去更新最大路径经过的节点数(左右子树深度之和再加一)
            :param root:
            :return:
            """
            if not root:
                return 0
            leftMaxDepth = getMaxDepth(root.left)
            rightMaxDepth = getMaxDepth(root.right)
            self.res = max(self.res, leftMaxDepth + rightMaxDepth + 1)  # 每次拿到左右子树的深度之和再加一之后，就去更新最大路径经过的节点数
            return max(leftMaxDepth, rightMaxDepth) + 1

        if not root:
            return 0
        getMaxDepth(root)
        return self.res - 1


if __name__ == "__main__":
    root = TreeNode(1)
    root.left, root.right = TreeNode(2), TreeNode(3)
    root.left.left, root.left.right = TreeNode(4), TreeNode(5)
    print(Solution().diameterOfBinaryTree(root))
